package 树;


import 抽象数据类型.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: yangwk37982
 * @date: 2022/4/26 13:23
 */
public class 修剪二叉搜索树 {
    public static void main(String[] args) {
        TreeNode<Integer> treeNode = new TreeNode<Integer>(6);
        treeNode.left = new TreeNode(3);
        treeNode.right = new TreeNode(10);
        treeNode.left.left = new TreeNode(1);
        treeNode.left.right = new TreeNode(4);
        treeNode.right.left = new TreeNode(7);
        treeNode.right.right = new TreeNode(11);
        TreeNode treeNode1 = trimBST1(treeNode, 4, 6);
        System.out.println(traverse(treeNode));
        System.out.println(traverse(treeNode1));

    }

    //遍历
    public static List<Integer> traverse(TreeNode<Integer> root) {
        List<Integer> result = new ArrayList<>();
        if (root != null) {
            result.addAll(traverse(root.left));
            result.add(root.val);
            result.addAll(traverse(root.right));
        }
        return result;
    }

    public static TreeNode<Integer> trimBST1(TreeNode<Integer> root, int low, int high) {
        // 如果是空直接返回
        if (root == null)
            return null;
        // 如果当前节点小于low，那么当前节点以及他的所有左子树都要被剪掉，
        TreeNode left = null;
        TreeNode right = null;
        if (root.val < low)
            return trimBST1(root.right, low, high);
        // 同上
        if (root.val > high)
            return trimBST1(root.left, low, high);
        // 否则当前节点要保留
        root.left = trimBST1(root.left, low, high);
        root.right = trimBST1(root.right, low, high);
        return root;
    }

    public static TreeNode trimBST(TreeNode<Integer> root, int low, int high) {
        if (root == null) {
            return null;
        }
        TreeNode left = trimBST(root.left, low, high);
        TreeNode right = trimBST(root.right, low, high);
        if (root.val < low) {
            return right;
        }
        if (root.val > high) {
            return left;
        }
        root.right = right;
        root.left = left;
        return root;
    }
}
